// 给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
// 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
// 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
// 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
// 五部曲
// 1. 确定dp数组，`dp[i][j]`,第i天状态为j，最多现金，有四种状态
//     1. **状态1**，持有股票，今天买入，或者之前就买入，现在持有
//     2. 不持有股票
//         1. **状态2**，保持卖出股票的状态，两天前卖出股票，度过了一天冷冻期，一天前卖出股票，没有操作
//         2. **状态3**，今天卖出股票  **这里单独设置状态是因为，状态4的前一天一定是卖出股票**
//     3. **状态4**，今天是冷冻期，只有一天
// 2. 确定递推公式
//     1. 状态1，持有股票
//         1. 今天买入
//             1. 前一天是保持卖出股票的状态，`dp[i-1][1] - prices[i]`
//             2. 前一天是冷冻期，`dp[i-1][3] - prices[i]`
//             3. `Math.max(dp[i-1][1] - prices[i], dp[i-1][3] - prices[i])`
//         2. 前一天就是持有股票，`dp[i-1][0]`
//         3. `dp[i][0] = Math.max(Math.max(dp[i-1][1] - prices[i], dp[i-1][3] - prices[i]), dp[i-1][0])`
//     2. 状态2，保持不持有股票
//         1. 前一天冷冻期，`dp[i-1][3]`
//         2. 前一天就是卖出的状态， `dp[i-1][1]`
//         3. `dp[i][1] = Math.max(dp[i-1][3], dp[i-1][1])`
//     3. 状态3，今天卖出股票,昨天一定是持有股票，`dp[i][2] = dp[i-1][0] + prices[i]`
//     4. 状态4，今天冷冻期，昨天一定卖出了股票，`dp[i][3] = dp[i-1][2]`
// 3. dp数组初始化
//     1. 状态1，`dp[0][0] = -prices[0]`
//     2. 状态2和状态3和状态4，`dp[0][1] = 0; dp[0][2] = 0;dp[0][3] = 0`
// 4. 遍历顺序从前往后
// 5. 举例推导

// 最后结果取状态2，状态3，状态4，的最大值

// 时间复杂度：O(n)
// 空间复杂度：O(n)

function maxProfit(prices) {
    // 0, 持有股票
    // 1. 不持有股票，两天前或者一天前卖了
    // 2. 不持有股票，今天卖了
    // 3. 冷冻状态，前一天刚卖股票
    let dp = new Array(prices.length).fill(0).map(_ => new Array(4).fill(0))
    dp[0][0] = -prices[0]
    for (let i = 1; i < prices.length; i++) {
        dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i], dp[i-1][3] - prices[i])    
        dp[i][1] = Math.max(dp[i-1][1], dp[i-1][3])
        dp[i][2] = dp[i-1][0] + prices[i]
        dp[i][3] = dp[i-1][2]
    }
    return Math.max(dp[prices.length - 1][1], dp[prices.length - 1][2], dp[prices.length - 1][3])
}

console.log(maxProfit([1,2,3,0,2]))